1. Field of the Invention
The present invention relates to 3-dimensional (3D) display, and more particularly, to a method and apparatus for efficiently processing a query required for 3D display or for running a game using 3D display.
2. Description of the Related Art
With the development of 3D display technologies, 3D display technologies have been applied to computer games and thus games employing 3D graphics (3D games) have become widely used. In the case of a 3D game, a large number of objects having motions in a large 3D space exist where each object may have a characteristic motion.
Such a 3D space is formed with a plurality of objects, and the objects can be broken down into geometric objects (ClumpObject), lights (LightObject) that light the 3D space, and cameras (CameraObject).
In order to display such a 3D space or to run the 3D games, queries are required to be processed. Queries that are required to be processed include a visibility query and a localization query. The visibility query is used to obtain information on objects that can be seen from a current camera viewpoint, and the localization query is used to obtain information on surrounding objects of interest from a current arbitrary position.
A great amount of computation power is required to process the queries in a large-scale 3D game or an ordinary 3D application formed in a 3D space including many objects. A general method of processing a visibility query is as follows.
A view frustum, which is a region seen by a current camera, is obtained. Visibility checking is performed in relation to each object existing in the corresponding 3D space to confirm whether or not the object exists in the view frustum. According to the result of the visibility checking, a list of objects that are determined to be in the view frustum is output.
Accordingly, if the number of objects existing in the 3D space is 100,000, for example, the visibility checking should be performed 100,000 times in order to process a visibility query for every object. Also, in the case of localization query processing, distance checking should be performed in which a distance to each and every object existing in the 3D space should be calculated. Accordingly, the distance checking should be performed the same number of times as the number of the objects. Thus, there has been a problem in that a huge amount of computation power is required in order to process queries for 3D display or for running a game using 3D display.